package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author durant
 * @create 2021-11-15 18:46
 */
public class RadixSort {
    public static void main(String[] args) {
//        int[] arr = {53, 3, 542, 748, 14, 214};
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        Date date1 = new Date(System.currentTimeMillis());
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("hh:mm:ss.SSS");
        String format = simpleDateFormat.format(date1);
        radixSort(arr);
        Date date2 = new Date(System.currentTimeMillis());
        String forma2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间：" + format);
        System.out.println("排序后的时间：" + forma2);

    }

    public static void radixSort(int[] arr) {
        // 先搞定第一轮，针对元素的个位数进行处理

        // 先创建10个桶，通过二维数组的方式进行创建
        int[][] bucket = new int[10][arr.length];
        // 为了记录每个桶中存放了多少个数据，即方便将桶中的数据取出，定义一个一维数组，用来记录
        int[] bucketElementCounts = null;
        int index = 0;
        int temp = 0;
        // 归纳
        for (int i = 1; i < arr.length; i++) {
            temp = arr[0];
            if (Math.abs(temp) < Math.abs(arr[i])) {
                temp = arr[i];
            }
        }
        // 得到最大位数
        int maxLength = (temp + "").length();

        for (int n = 0,c = 1; n < maxLength; n++,c *= 10) {// n代表第几轮，如果最大数是1000 ，那么n=3
            bucketElementCounts = new int[10];
            for (int j = 0; j < arr.length; j++) {
                //取出元素的个位
                int digitOfElement = arr[j] / c % 10; // 十位
//                int digitOfElement = arr[j] / (10 ^ n) % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            index = 0; // 按照桶的顺序进行取出数据，表示原数组的下标
            // 在桶中放完数据后，将桶中的数据取出
            for (int i = 0; i < bucketElementCounts.length; i++) {
                // 如果桶中有数据，才将其放入到数组中
                if (bucketElementCounts[i] != 0) {
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        // 取出数据放入数组
                        arr[index] = bucket[i][j];
                        index++;
                    }
                }
            }
        }







        /*
        // 第一轮
        for (int j= 0; j<arr.length; j++){
            //取出元素的个位
            int digitOfElement = arr[j] % 10; // 个位
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        int index = 0; // 按照桶的顺序进行取出数据，表示原数组的下标
        // 在桶中放完数据后，将桶中的数据取出
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据，才将其放入到数组中
            if (bucketElementCounts[i] != 0 ){
                for (int j = 0; j < bucketElementCounts[i] ; j++) {
                    // 取出数据放入数组
                    arr[index] = bucket[i][j];
                    index++;
                }
            }
        }
        // 十位
        // 第二轮
        bucketElementCounts = new int[10];
        for (int j= 0; j<arr.length; j++){
            //取出元素的个位
            int digitOfElement = arr[j]/10%10; // 十位
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        index = 0; // 按照桶的顺序进行取出数据，表示原数组的下标
        // 在桶中放完数据后，将桶中的数据取出
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据，才将其放入到数组中
            if (bucketElementCounts[i] != 0 ){
                for (int j = 0; j < bucketElementCounts[i] ; j++) {
                    // 取出数据放入数组
                    arr[index] = bucket[i][j];
                    index++;
                }
            }
        }

        // 百位
        // 第二轮
        bucketElementCounts = new int[10];
        for (int j= 0; j<arr.length; j++){
            //取出元素的个位
            int digitOfElement = arr[j]/100%10; // 百位
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        index = 0; // 按照桶的顺序进行取出数据，表示原数组的下标
        // 在桶中放完数据后，将桶中的数据取出
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据，才将其放入到数组中
            if (bucketElementCounts[i] != 0 ){
                for (int j = 0; j < bucketElementCounts[i] ; j++) {
                    // 取出数据放入数组
                    arr[index] = bucket[i][j];
                    index++;
                }
            }
        }
        */

    }
}
